package com.leetcode;

/**
 * 斐波那契数列
 * f(0) = 1, f(1) = 1
 * f(n) = f(n-1) + f(n-2)
 *
 * 解题思路：
 *  1、递归
 *  2、递归可以转换成树来操作，避免重复，对于已经计算过的几点，使用字典，无需重复计算
 *  3、暴力解法：时间复杂度O(2^n)，空间复杂度O(n)
 *  4、记忆化递归法：时间复杂度O(n)，空间复杂度O(n)
 *  5、动态规划：时间复杂度O(n)，空间复杂度O(1)
 */
public class Offer10 {
    public static void main(String[] args) {
        int n = 30;
        // TODO 额外存储空间
        int[] dict = new int[n];
        for (int i = 0; i < n; i++) {
            dict[i] = -1;
        }
        System.out.println("f(" + n + ") = " + fnum(dict, n) % 1000000007);
        System.out.println("f(" + n + ") = " + fnum2(n));
    }

    /**
     * 斐波那契数列
     *      时间复杂度
     *      空间复杂度O(n)，因为用了disct用来存储已经计算过的字典
     *      问题：如果n大了之后，dict会有越界风险
     * @param dict
     * @param n
     * @return
     */
    public static int fnum(int[] dict, int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        int f1 = 0;
        if (dict[n-1] != -1) {
            f1 = dict[n-1];
        }
        else {
            f1 = fnum(dict, n-1);
            dict[n-1] = f1;
        }
        int f2 = 0;
        if (dict[n-2] !=-1) {
            f2 = dict[n-2];
        }
        else {
            f2 = fnum(dict, n-2);
            dict[n-2] = f2;
        }
        return f1 + f2;
    }

    /**
     * 空间复杂度O(1)
     * f(n)%100000007 = (f(n-1) + f(n-2)) % 1000000007
     * @param n
     * @return
     */
    public static int fnum2(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;

        // TODO fn1 保存n-1的值, fn2 保存n-2的值
        int fn1 = 1, fn2 = 0, sum = -1, tmp = -1;
        for (int i = 2; i <= n; i++) {
            // f2 = fn1 + fn2;
            sum = (fn1 + fn2) % 1000000007;

            // TODO fn1指向sum，fn2指向原来的fn1
            tmp = fn1;
            fn1 = sum;
            fn2 = tmp;
        }
        return sum;
    }
}
